package com.sicheng.lc.杂题.二分技巧;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/18 16:49
 */
public class 找出第K小的数对距离 {
    //https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
    //  二分经典题目  用答案区间来check
    //   也是leftSearch原生的模板
    //   搜索的值满足可否找到一个更小的数满足
    //   搜索的值不满足直接更新l
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = (int) 1e6;
        while (l <= r) {
            int mid = l + r >> 1;
            // 在距离d之内的数对的个数小于k
            // 说明d过小 适当增大 d
            int n = check(nums, mid);
            if (n < k) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    // 其实这道题涉及到2个板子
    // 第一个就是leftSearch
    // 还有一个就是双指针滑动的板子 我lc/双指针 目录应该收录了很多双指针
    // 总体而言就是不断滑r，然后某个条件不成立就滑l
    // 没必要死记硬背 板子在手天下我有 平时注重积累 考试自然而然就有了
    // 今年高考不是也说了 秒手是非常难得的必须得日复一日的平手或得妙手
    private int check(int[] nums, int d) {
        int res = 0;
        int l = 0;
        for (int r = 1; r < nums.length; r++) {

            while (nums[r] - nums[l] > d) {
                l++;
            }
            res += r - l;
        }
        return res;
    }


}
